/**
 * Created by zhourh on 2018/6/21.
 *
 * 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

 示例 1:

 输入: 二叉树: [1,2,3,4]
 1
 /   \
 2     3
 /
 4

 输出: "1(2(4))(3)"

 解释: 原本将是“1(2(4)())(3())”，
 在你省略所有不必要的空括号对之后，
 它将是“1(2(4))(3)”。
 示例 2:

 输入: 二叉树: [1,2,3,null,4]
 1
 /   \
 2     3
 \
 4

 输出: "1(2()(4))(3)"

 解释: 和第一个示例相似，
 除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
 */
public class ConstructStringFromBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(4);

        System.out.println(new ConstructStringFromBinaryTree().tree2str(root));
    }

    public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }

        StringBuilder str = new StringBuilder(String.valueOf(t.val));

        // 左右子树只要有一个不为空，就需要输出左子树
        if (t.left != null || t.right != null) {
            tree2str(t.left, str);
        }
        if (t.right != null) {
            tree2str(t.right, str);
        }

        return str.toString();
    }

    public void tree2str(TreeNode t, StringBuilder preStr) {
        preStr.append("(");
        if (t != null) {
            preStr.append(t.val);
            // 左右子树只要有一个不为空，就需要输出左子树
            if (t.left != null || t.right != null) {
                tree2str(t.left, preStr);
            }
            if (t.right != null) {
                tree2str(t.right, preStr);
            }
        }
        preStr.append(")");
    }
}
